/*
题目链接：https://leetcode.cn/problems/count-special-integers/description/
2376. 统计特殊整数-困难
完成日期：2024/10/7
数位DP
*/

class Solution {
public:
    int countSpecialNumbers(int n) {
        string s = to_string(n);
        int len = s.length();
        vector<vector<int>> m(len, vector<int>(1 << 10, -1));
        auto dfs = [&](auto&& dfs, int i, int mask, bool l, bool le) -> int {
            if (i == len) {
                return le;
            }
            if (!l && le && m[i][mask] != -1) {
                return m[i][mask];
            }
            int res = 0;
            if (!le) { 
                res = dfs(dfs, i + 1, mask, false, false);
            }
            int up = l ? s[i] - '0' : 9;
            for (int j = le ? 0 : 1; j <= up; j++) {
                if ((mask >> j & 1) == 0) {
                    res += dfs(dfs, i + 1, mask | (1 << j), l && j == up, true);
                }
            }
            if (!l && le) {
                m[i][mask] = res;
            }
            return res;
        };
        return dfs(dfs, 0, 0, true, false);
    }
};
